1. Field of the Invention
This invention relates generally to hard disk error correction code decoders, and more particularly to devices and methods for solving error locator polynomials.
2. Description of the Related Art
Modern computer systems generally include one or more hard disk drives to store large amount of data and programs. Hard disk drives typically store information in sequence by using magnetic technology. Like most recording technology, reading the sequential data bits from a hard disk often generates errors due to noise, manufacturing imperfections of the physical medium, dust, etc.
To detect and correct such errors, hard disk drives typically implement an error correction code (ECC) scheme in writing to and reading from hard disk drives. These hard disk drives generally include ECC circuitry that implement ECC schemes using well known codes such as Reed-Solomon codes to encode user data for reliable recovery of the original data through an ECC decoder. This helps to achieve a higher areal density.
Conventional ECC schemes compute ECC bytes for a given block of user data such as a data sector. The computed ECC bytes are appended to the block of user data sector and then recorded on a hard disk. When the entire sector is read, the ECC approach computes error locations and error patterns in the user data by decoding the ECC bytes.
Prior Art FIG. 1 illustrates a block diagram of a conventional computer system 100 including a host computer 118 that receives data from a disk 102 in a hard disk drive. A motor 104 spins the disk 102 containing the data. A read/write head 106 attached to an actuator 108 searches for a track and sectors that contain the desired data. Upon finding the desired sectors, the read/write head 106 reads the data sequentially from the disk 102. An amplifier 110 amplifies the data signals and transmits the amplified data signals to an analog-to-digital converter 112.
The analog-to-digital converter 112 converts the amplified data signals into digital data bits and transmits the data bits to a deserializer 114. The deserializer 114 receives the sequential data bits and converts the data into a series of blocks called sectors, each of which is typically 512 bytes of user data and ECC bytes appended to the user data bytes. The deserializer 114 sequentially transmits the sectors to an error detection and correction (EDAC) circuitry 116, which detects errors in the received sector and, if correctable, corrects the detected errors using an ECC scheme. The EDAC circuitry 116 then transmits the error corrected user data to the host computer 118.
The EDAC circuitry 116 typically employs a conventional Reed-Solomon code in its ECC scheme to encode user data for reliable recovery of the original data. Under the Reed-Solomon code ECC scheme, assuming .LAMBDA.(z) is an error locator polynomial that has its roots the inverses of the .nu. error locators {.alpha..sup.i.sup..sub.k }, then the error locator polynomial .LAMBDA.(z) can be expressed as: ##EQU1##
Equation (2) can be used to evaluate the error locator polynomial .LAMBDA.(z) at all nonzero field elements, .alpha..sup.0 to .alpha..sup.2.sup..sup.b .sup.-2 in a finite field, where b is the number of bits in a symbol (e.g., byte). For example, for a byte containing 8 bits, the field GF(2.sup.8) includes 255 field elements from .alpha..sup.0 to .alpha..sup.254. The error locator polynomials and Galois fields are well known in the art and is described, for example, in Error Control Systems for Digital Communication and Storage, by Stephen B. Wicker, 1995, ISBN 0-13-200809-2, which is incorporated herein by reference.
Prior Art FIG. 2 shows a more detailed block diagram of the EDAC circuitry 116 that utilizes the ECC scheme. The EDAC circuitry 116 receives a sector 200 of user data bytes of 512 bytes and additional ECC bytes in a sequential manner. At the front end of the EDAC circuitry 116, a syndrome generator 202 receives the sector 200 and generates partial syndromes from the received sector data. Syndrome generators are well known in the art and are typically implemented as a linear feedback shift register circuit. The generated partial syndrome indicates whether an error is present in the received sector 200. For example, a zero syndrome indicates that no error has been detected. On the other hand, a nonzero syndrome indicates that one or more errors has been detected in the received data.
The generated partial syndromes are then transmitted to an ECC decoder 204, which includes error locator polynomial generator 206, an error locator polynomial solver 208, and an error pattern generator 210. The error locator polynomial generator 206 receives the partial syndromes from the syndrome generator 202 and generates a set of coefficients (i.e., .LAMBDA..sub.i s) for the received sector 200. The generated set of coefficients defines an error locator polynomial. Using the coefficients defining the error locator polynomial, the error locator polynomial solver 208 sequentially computes the error locations (e.g., byte locations) in the received sector by determining the roots of the error locator polynomial and feeds the error locations to the error pattern generator 210. The error pattern generator 210 computes error patterns in the received sector 200 using the error locations and partial syndromes. The EDAC circuitry 116 then uses the error locations and error patterns to correct the errors in the received sector.
The error locator polynomial solver 208 is typically implemented by means of a conventional Chien search technique to determine error locations, .alpha..sup.i s, from the coefficients of an error locator polynomial, .LAMBDA.(z). The Chien search technique is a systematic means of evaluating the error locator polynomial at all elements in a field GF(2.sup.m). Each coefficient .LAMBDA..sub.i of the error locator polynomial, for i greater than 0, is repeatedly multiplied by .alpha..sup.i. Each set of the products is then summed and compared with 1. If the sum is equal to 1, then .alpha..sup.i is a root of the error locator polynomial, .LAMBDA.(z), and an error is indicated at the coordinate or location associated with .alpha..sup.-i =.alpha..sup.n-i, where the data bytes in a received sector are labeled (r.sub.0, r.sub.1, . . . , r.sub.n-1). Chien search techniques and circuits are well known in the art and are described, for example, in Error Control Systems for Digital Communication and Storage, Stephen B. Wicker, 1995, ISBN 0-13-200809-2, on pages 204-211, the disclosure of which is incorporated herein by reference.
Prior Art FIG. 3 illustrates a conventional Chien search circuit 208 for finding a set of error locations by evaluating an error locator polynomial at all elements from .alpha..sup.0 to .alpha..sup.254 sequentially in a field GF(2.sup.8). In particular, the Chien search circuit 208 determines the roots to the error locator polynomial defined by a set of coefficients including .LAMBDA..sub.1, .LAMBDA..sub.2, .LAMBDA..sub.3, .LAMBDA..sub.4, .LAMBDA..sub.5, and .LAMBDA..sub.6 (.LAMBDA..sub.1 to .LAMBDA..sub.6 hereinafter). The Chien search circuit 208 includes a set of storage elements 302, 304, 306, 308, 310, and 312 (302 to 312 hereinafter), which initially receive and store the set of coefficients, .LAMBDA..sub.1 to .LAMBDA..sub.6, respectively.
Each of the storage elements 302 through 312 is associated with a constant GF multiplier, which is well known in the art. Specifically, the storage elements 302 to 312 are coupled to constant multipliers 318, 320, 322, 324, 326, and 328 (318 to 328 hereinafter), respectively, in a feedback configuration. The constant multipliers 318 to 328, respectively, are operative to multiply constants .alpha..sup.1, .alpha..sup.2, .alpha..sup.3, .alpha..sup.4, .alpha..sup.5, and .alpha..sup.6, respectively, with the coefficients .LAMBDA..sub.1, .LAMBDA..sub.2, .LAMBDA..sub.3, .LAMBDA..sub.4, .LAMBDA..sub.5, and .LAMBDA..sub.6. The resulting products are then stored back in the associated storage elements 302 to 312 in a feedback configuration. Accordingly, each of the storage elements 302 to 312 provides a coefficient or a product to the associated constant multiplier, which then feeds the result back to the associated storage element for storage.
The Chien search circuit 208 also includes a conventional Galois Field (GF) adder 314 and a comparator 316. At each clock cycle, the Chien search circuit sequentially increments .alpha..sup.i from .alpha..sup.0 to .alpha..sup.254 by means of a counter. At the same time, the contents of the storage elements 302 through 312 are fed to the adder 314 to generate a sum. The sum is then fed to the comparator, which compares the sum to a constant value, 1. If the sum is equal to the constant value, the particular .alpha..sup.i in the counter is output as a root of the error locator polynomial. This process repeats for all the field elements sequentially from .alpha..sup.0 to .alpha..sup.254 to find the roots.
Unfortunately, the conventional Chien search circuit 208 is not very efficient in finding the roots of an error locator polynomial. Specifically, since the Chien search circuit 208 tests each of the 255 field elements sequentially, it requires 255 clock cycles to determine if each of the field elements is a root. Accordingly, the Chien search circuit 208 takes 255 clock cycles to find all the roots to the error locator polynomial.
Thus, what is needed is a circuit and a method that can determine the roots of an error locator polynomial in a more efficient and timely manner.